package main;

import java.util.Random;

/*
 * The method solve(int, int, int[][]),
 * legal(int, int, int, int[][]),
 * and writeMatrix(int[][]) are from the following web address.
 * http://www.colloquial.com/games/sudoku/java_sudoku.html
 */
/**
 * 
 * @author Peng
 *
 */
public class Sudoku {

	private final static int size=9;
	public static final int EASY=30;
	public static final int MEDIAN=25;
	public static final int HARD=20;
	public static final String sudokuStr="459378126263591847178624953521963478794185362836742519642819735915237684387456291";
	

	/**
	 * Solves the sudoku matrix.
	 * @param i, the row number
	 * @param j, the colunm number
	 * @param cells, the sudoku matrix.
	 * @return true if solved, else false.
	 */
    public static boolean solve(int i, int j, int[][] cells) {
		if (i == 9) {
		    i = 0;
		    if (++j == 9) 
			return true; 
		}
		if (cells[i][j] != 0)  // skip filled cells
		    return solve(i+1,j,cells);
		
		for (int val = 1; val <= 9; ++val) {
		    if (legal(i,j,val,cells)) {  
			cells[i][j] = val;       
			if (solve(i+1,j,cells))  
			    return true;
		    }
		}
		cells[i][j] = 0; // reset on backtrack
		return false;
    }

    /**
     * Check if a value in the matrix is legal.
     * @param i, the row number.
     * @param j, the column number.
     * @param val, the value to be checked.
     * @param cells, the matrix.
     * @return true if is legal, else false.
     */
    public static boolean legal(int i, int j, int val, int[][] cells) {
		for (int k = 0; k < 9; ++k)  // row
		    if (val == cells[k][j])
			return false;
	
		for (int k = 0; k < 9; ++k) // col
		    if (val == cells[i][k])
			return false;
	
		int boxRowOffset = (i / 3)*3;
		int boxColOffset = (j / 3)*3;
		for (int k = 0; k < 3; ++k) // box
		    for (int m = 0; m < 3; ++m)
			if (val == cells[boxRowOffset+k][boxColOffset+m])
			    return false;
	
		return true; // no violations, so it's legal
    }
    
    /**
     * Check if a matrix is a legal sudoku matrix
     * @param matrix, the matrix to be checked
     * @return true if it's legal, else false;
     */
    public static boolean isLegalMatrix(int [][] matrix)
    {
    	int tmp=0;
    	for(int r=0; r<size; r++)
    	{
    		for(int c=0; c<size; c++)
    		{
    			if(matrix[r][c] !=0 )
    			{
    				tmp=matrix[r][c];
    				matrix[r][c]=0;
    				if(!legal(r,c,tmp,matrix))
    				{
    					System.out.println("ilegal");
    					return false;
    				}
    				matrix[r][c]=tmp;
    			}
    		}
    	}
    	return true;
    }
    
    /**
     * Make sudoku for sudokuSolution() method.
     * @return a final sudoku
     */
    public static int[][] createSudoku() 
    {	
    	int[][] sudoku=new int[size][size];
    	initialSudoku(sudoku);
    	Random ran=new Random();
    	boolean go=true;
    	
    	for(int i=0; i<11;i++)	   
    	{	   
    		int r=0, c=0;//row, col
    		int gridNum;
    		go=true;
    		r=ran.nextInt(9);	    		
    		c=ran.nextInt(9);
    		gridNum=ran.nextInt(9)+1;
		   
    		while(go)	    	
    		{	
			   r=ran.nextInt(9);	    		
			   c=ran.nextInt(9);
			   gridNum=ran.nextInt(9)+1;
			   if(sudoku[r][c] ==0 && legal(r,c,gridNum,sudoku))
			   {
				   go=false;
				   sudoku[r][c]=gridNum;
			   }
			   else
			   {
				   go=true;
			   }
		   }
	   }
    	//writeMatrix(sudokuSolution);
    	return sudoku;
    }
    
    /**
     * Create a initial sudoku matrix with 9 difffernt digits.
     * Only used by createSudoku()
     * @param sudoku
     */
    
    private static void initialSudoku(int[][] sudoku) 
    {	
    	Random ran=new Random();
    	boolean go=true;
    	
    		   
		for(int gridNum=1;gridNum<10;gridNum++)
		{
			int r=0, c=0;//row, col
    		go=true;
		   
    		while(go)	    	
    		{	
			   r=ran.nextInt(9);	    		
			   c=ran.nextInt(9);
			   if(sudoku[r][c] ==0 && legal(r,c,gridNum,sudoku))
			   {
				   go=false;
				   sudoku[r][c]=gridNum;
			   }
			   else
			   {
				   go=true;
			   }
		   
    		}
		}
    	
    	//writeMatrix(sudokuSolution);
    	return;
    }
    
    
    /**
     * Make a sudoku matrix solution
     * @return a sudoku matrix solution
     */
    public static int[][] sudokuSolution()
    {
    	int[][] solution = new int[size][size];
    	boolean go=true;
    	while(go)
    	{
    		solution = createSudoku();
	    	if(solve(0,0,solution))
	    	{
	    		go=false;
	    		return solution;
	    	}
	    	else
	    	{
	    		return parseToInt(sudokuStr);
	    	}
    	}
    	
    	return solution;
    }
    

    
    /**
     * Converting the sudoku string to int[][]
     * @param s, the input sudoku string
     * @return sudoku matrix in int [][]
     */
    public static int[][] parseToInt(String s)
    {
    	int [][] solution = new int[size][size];
    	char[] sol=s.toCharArray();
    	int index=0;
    	
    	for(int r=0; r<size; r++)
    	{
    		for(int c=0; c<size; c++)
    		{
    			solution[r][c]=sol[index]-48;//assci 0-9 is 48-57
    			index++;
    		}
    	}
    	return solution;
    }
    
    /**
     * Converting a sudoku matrix into a string
     * @param matrix, the input integer matrix
     * @return a string representative of the matrix
     */
    public static String parseToStr(int[][] matrix)
    {
    	String matrixStr="";
    	for(int r=0; r<size; r++)
    	{
    		for(int c=0; c<size; c++)
    		{
    			matrixStr=matrixStr+Integer.toString(matrix[r][c]);
    		}
    	}
    	
    	return matrixStr;
    }
    
    /**
     * Making the final sudoku matrix with specified level.
     * @param solution , the solution matrix of the sudoku
     * @param level, the level of the game you want to create
     * @return a sudoku matrix of specified level.
     */
    
    public static int [][] sudokuLevel(int [][]solution, int level)
    {
    	int[][]sudokuLevel = new int[size][size];
    	
    	Random ran = new Random();
    	int row, col;
    	boolean go=true;
    	for(int i=0; i<level; i++)
    	{
    		
    		go=true;
    		while(go)
    		{
    			row=ran.nextInt(9);
        		col=ran.nextInt(9);
        		if(sudokuLevel[row][col]==0)
        		{
        			sudokuLevel[row][col]=solution[row][col];
        			go=false;
        		}
    		}
    	}
    	
    	return sudokuLevel;
    }
    
    /**
     * Print a formated matrix.
     * @param solution
     */
    static void writeMatrix(int[][] solution) {
		for (int i = 0; i < 9; ++i) {
		    if (i % 3 == 0)
			System.out.println(" -----------------------");
		    for (int j = 0; j < 9; ++j) {
			if (j % 3 == 0) System.out.print("| ");
			System.out.print(solution[i][j] == 0
					 ? " "
					 : Integer.toString(solution[i][j]));
			
			System.out.print(' ');
		    }
		    System.out.println("|");
		}
		System.out.println(" -----------------------");
	    }
    
    /**
     * Print the matrix in a string.
     * @param solution
     */
    public static void printMatrixInStr(int[][]solution)
    {
    	for(int r=0; r<size; r++)
    	{
    		for(int c=0; c<size; c++)
    		{
    			System.out.print(solution[r][c]);
    		}
    	}
    	System.out.println();
    }


}
